package com.zbcn.structure.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description: 无向图
 * @author likunn
 * @date 2024/8/19 13:56
 * @version 1.0
 */
public class UndirectedGraph {

    /**
     * 顶点个数
     */
    private int v;

    /**
     * 临接表
     */
    private LinkedList<Integer> adj[];


    public UndirectedGraph(int v){
        this.v = v;
        for (int i= 0; i <v; i++){
            adj[i] = new LinkedList<>();
        }
    }

    /**
     * 无向图一条边存储两次
     * @param s 开始顶点
     * @param t 终止顶点
     */
    public void addEdge(int s, int t){
        adj[s].add(t);
        adj[t].add(s);
    }

    /**
     * Breadth first search 广度优先搜索： 逐层访问的，即：我们把k层的顶点访问完后，才能访问第 k+1 层的顶点
     * @param s 起始顶点
     * @param t 结束顶点
     */
    public void bfs(int s, int t){
        if (t == s){
            return;
        }
        // 存储已经被访问的顶点，用来避免顶点被重复访问，（下标为 顶点、 value 表示是否被访问（如果访问，表示true））
        boolean[] visited = new boolean[v];

        visited[v] = true;
        // 用来存储自己已经被访问，但是相连的顶点还没有被访问的顶点。
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        // 用来记录搜索路径，从顶点 s 开始，广度优先搜索到顶点 t 后，存储的就是搜索路径，这个路径是反响的， prev[w] 存储的是 顶点 w 使用哪个前驱节点遍历过来的
        int[] prev =  new int[v];
        // 起始顶点没有前驱节点
        for (int i= 0; i < prev.length; i++){
            prev[i] = -1;
        }
        // 如果还有节点没有被访问
        while (queue.size() > 0){
            // 获取没有被访问的顶点
            int w = queue.poll();
            // 顶点对应的链
            LinkedList<Integer> linkAdj =  adj[w];
            for (int i= 0; i < linkAdj.size(); ++i){
                // 获取链上的节点
                int q = linkAdj.get(i);

                // 判断节点有没有被访问过
                if (!visited[q]){
                    // 记录访问路径
                    prev[q] = w;
                    // 表示已经访问到了尾节点
                    if (q == t){
                        print(prev,s,t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    // 递归打印 s - t 的路径
    private void print(int[] prev, int s, int t) {
        if (prev[t] != -1   // 代表 t 还有前驱节点
                && t != s){
            // 打印前驱节点
            print(prev,s,prev[t]);
        }

        System.out.println(t + " ");
    }

    /**
     * Depth first search 深度优先搜索： 一种重要的思想，回溯思想
     * @param s 起始顶点
     * @param t  终止顶点
     */
    public void dfs(int s, int t){
        // 用来判断是否已经找到
        boolean found = false;

        // 记录已经被访问的节点
        boolean[] visited = new boolean[v];
        visited[s] = true;
        //记录访问路径，数组的 index 表示当前节点， index 对应的 value 表示 前驱节点
        int[] prev = new int[v];
        for (int i = 0 ; i < prev.length; i++){
            prev[i] = -1;
        }

        //回溯遍历，递归
        recurDfs(s,t,visited,prev,found);
        // 打印路径
        print(prev,s,v);

    }

    private void recurDfs(int w, int t, boolean[] visited, int[] prev, boolean found) {
        if (found == true){
            return;
        }

        visited[w] = true;
        // 已经到了终点
        if (w == t){
            found = true;
            return;
        }

        // 深度优先搜索的核心逻辑
        LinkedList<Integer> listAdj = adj[w];
        for (int i = 0; i < listAdj.size(); ++i){
            int q = listAdj.get(i);
            if (!visited[q]){
                prev[q] = w;
                recurDfs(q,t,visited,prev,found);
            }
        }
    }

}
